A digital network is comprised of a group of switches (nodes) that are connected to each other through a variety of interfaces. Asynchronous Transfer Mode (“ATM”) or “cell switching” is a technology designed for transmitting digital information such as voice, video, and data at high speeds through the digital network. The digital information is segmented into cells (fixed-length packets) and transmitted from a source node through various intermediate nodes to a destination node. The path traversed through the network is known as a connection.
A digital network may employ virtual circuits that appear to be a discrete physical circuit dedicated to a particular user, but are actually a shared pool of circuit resources used to support multiple users. A permanent virtual circuit (PVC) is a continuously dedicated virtual circuit while a switched virtual circuit (SVC) is a temporary virtual circuit that may be dynamically established on demand, but is maintained only for the duration of a data transfer session. A hybrid of the PVC and the SVC is the soft permanent virtual circuit (SPVC) that has a PVC at the end points with a SVC within the network. This provides the user with the appearance and benefit of a PVC, but allows the network to intelligently reroute calls to accommodate node failures and optimize bandwidth utilization.
FIG. 1 illustrates an exemplary digital network in accordance with the prior art. Network 100 includes a plurality of nodes A-H that are interconnected by network connections (links) 101-111. The links transfer data from an originating customer-premise equipment (CPE) node CPE1 to a terminating CPE node CPE2. Each CPE node is terminating hardware such as a workstation, a computer, a server, or similar device that is owned by the user and not a service provider.
In general, the network 100 may include a variety of networks (e.g., ATM) coupling a plurality of users. Network 100 employs a SPVC so that network connections 101 and 111 are PVCs while the remaining connections are SVCs. A connection between users (or between particular nodes) may be established by traversing various combinations of intermediate nodes and links. For example, a connection between CPE1 and CPE2 may be comprised of nodes A-E and links 101-105 and 111 or may be comprised of nodes A, F, G, H, and E, and links 101 and 107-111.
A particular path is selected based upon a number of metrics including cell transfer delay (CTD), cell delay variation (CDV), and administrative weight (AW). These criteria are evaluated on a link-by-link basis, and totaled to determine a path cost. The CTD is the elapsed time between when a particular cell leaves a source node and when it enters a destination node. The CTD is the sum of the total inter-node transmission time and the total node processing time. The CDV is the variation of the CTD that may be induced by buffering and cell scheduling and is based on the probability of a cell arriving at a destination node later than expected. The AW is a weight for each link that may represent monetary cost, length of cable, direction of traffic, or other considerations or combinations thereof.
The routing protocol (e.g., Private Network to Network Interface (PNNI)) uses the metrics to route a call (establish a connection) based on a cost requirement. For example, some connections may have maximum CTD or CDV requirements.
The CTD and the CDV are link characteristics that are measured dynamically and continuously. The AW on the other hand is a static value determined by a network operator based on a number of criteria as discussed above and is not subject to continuous revision.
Currently, switches, such as the MGX 8850 switch available from Cisco Systems, Incorporated of San Jose, Calif., provide the capability of cost-based connection grooming (optimization) for SPVCs. The cost of the route will be the sum of the additive metrics on each link. For source routing protocols (e.g., PNNI), the routing cost of the SPVC is determined at the time of route selection itself. For example, referring again to FIG. 1, the cost of a connection from CPE1 to CPE2 is determined while routing the call initially so a connection over nodes A-E and links 101-105 is determined by adding the cost of each link over the round trip path for a total cost of 40320. Because this is less than the cost of a connection over nodes A, F, G, H, and E, and links 107-111 (50400), the connection will be routed over nodes A-E and links 101-105. During grooming, if a path is available with a better cost to route the SPVC, then the SPVC is torn down (terminated) and re-established on the current optimal route.
This method of path optimization has several disadvantages that may lead to routing a call over a less than optimal path. The source node cannot ascertain with certainty the actual connection that will be established due to dynamic routing in a SPVC. The source node therefore presumes a connection, evaluates its cost and compares this cost to other presumed connections. For example, in the case of crankback, where a call cannot proceed on a desired link (e.g., due to a dynamic link failure) the peer node will choose another link that goes to the desired node. For example, in FIG. 1, node D has two links that go to node E, namely links 105 and 106. If link 105 fails, the call proceeds over link 106. However, the source node (node A) that determines the cost at the time the call is set up does not become aware of this dynamic selection of links in a SPVC. As illustrated by FIG. 1, this may lead to a less than optimal path being selected as the cost of routing the call over nodes A-E and links 101-104 and 106 is 60480 which is higher than the cost of a connection over nodes A, F, G, H, and E, and links 107-111 (50400). Also, the source node calculates path cost based on AW, but doesn't have other information that an intermediate node may use to dynamically route a call. For example, even if link 105 is available, node D may choose to route the call over link 106 based on other criteria such as load balancing algorithms or bandwidth availability.
Additionally, the current method of path optimization poses an inherent problem in a PNNI multi-peer group network. In a PNNI network, the cost of each link is advertised in the link topology state element. The PNNI topology state element (PTSE) is a collection of information that is flooded among all logical nodes within a peer group. The PNNI protocol exchanges these PTSEs through database synchronization and those PTSEs will be available in all nodes within the same peer group. However the cost of a link is not known beyond its peer group. So, for a call that crosses two or more peer groups, the routing cost will not take into consideration the cost of the internal links within the other peer group. For example, nodes A, B, C, and F of FIG. 1 may constitute one peer group, and nodes D, E, G, and H may constitute another. In such a case the originating node, node A can calculate the partial path cost over nodes B and C and links 102 and 103, and can calculate the partial path cost over node F and link 107, but does not have sufficient information to calculate an end-to-end path between CPE1 and CPE2, and therefore cannot effect efficient grooming.